Python3使用递归求斐波那契数列 |
您所在的位置：网站首页 › python 求斐波那契数列 › Python3使用递归求斐波那契数列 |
|
1. 递归函数
递归函数就是在函数中调用它自身，其主要用于将复杂问题分解为多个子问题，然后再对子问题进行拆分，分解成更小的问题，直到不能再拆分为止。 为了防止递归函数无休止地进行，必须在函数内有终止条件。 2. 递归函数的最大深度在Python中递归函数的最大深度是997 def func(n): print(n) n += 1 func(n) func(1) 3. 重置递归函数的最大深度 import sys print(sys.setrecursionlimit(2000)) def func(n): print(n) n += 1 func(n) func(1) 4. 递归函数示例 4.1 计算阶乘 n! ''' 分析： n! = 1*2*3*4*....(n-2)*(n-1)*n 我们使用函数 fact(n) 来表示n! ,即 fact(n) = n! n! = 1*2*3*4*....(n-2)*(n-1)*n = fact(n) (n-1)! = 1*2*3*4*....(n-2)*(n-1) = fact(n-1) 可以推导出： n! = fact(n-1) * n 同理，fact(n-1) = fact(n-2)*(n-1) ...... 直到 n=1 即 1! = 1 的时候不再进行分解； ''' def fact(n): if n == 1: return 1 return n*fact(n-1) print(fact(5)) # 120 ''' 5! 执行过程如下： 5*fact(4) 5*(4*fact(3)) 5*(4*(3*fact(2))) 5*(4*(3*(2*fact(1)))) 5*(4*(3*(2*1))) ''' 4.2. 斐波纳契数列斐波纳契数列：1，1，2，3，5，8，13…（该数列中，有n个数字，从第三个数字开始：数值 =前第一个数字 + 前面第二个数字）即：n=(n-2)+(n-1) # 1，1，2，3，5，8，13,21,34,55,...... def Fibonacci(n): if n== 1 or n == 2: return 1 else: return Fibonacci(n-1) + Fibonacci(n-2) print(Fibonacci(9)) 4.3. 求x的n次方 # 求x的n次方（n大于等于0），即n个x相乘 def func(x,n): if n == 0: return 1 else: return func(x,n-1) * x print(func(3,10)) 4.4 递归求斐波那契数列以下代码使用递归的方式来生成斐波那契数列： def recur_fibo(n): """递归函数 输出斐波那契数列""" if n |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |